// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

// 求在该柱状图中，能够勾勒出来的矩形的最大面积。

//  



// 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

//  



// 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

//  

// 示例:

// 输入: [2,1,5,6,2,3]
// 输出: 10

#include <vector>
#include <algorithm>
#include <stack>

using std::stack;
using std::vector;
using std::min;
using std::max;

class Solution1 {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res{0};
        int n{heights.size()};
        for (int i{0}; i < n; ++i) {
            if (i + 1 < n && heights[i] <= heights[i + 1]) continue;
            // 遇到局部峰值
            int minH = heights[i];
            for (int j{i}; j >= 0; --j) {
                minH = min(minH, heights[j]); // 前面的最矮值
                int area = minH * (i - j + 1);
                res = max(res, area); // 每向前一次都要比较结果
            }
        }
        return res;
    }
};

// 遇到的较小的数字只是一个触发，表示现在需要开始计算矩形面积了，
// 为了使得最后一块板子也被处理，这里用了个小 trick，在高度数组最后面加上一个0，这样原先的最后一个板子也可以被处理了
// 由于我们先取出栈中最高的板子，那么就可以先算出长度为1的矩形面积了，
// 然后再取下一个板子，此时根据矮板子的高度算长度为2的矩形面积，
// 以此类推，直到数字大于栈顶元素为止，再次进栈
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res{0};
        stack<int> st{};
        heights.push_back(0); // 为了处理最后一个
        int n = heights.size();
        for (int i{0}; i < n; ++i) {
            // 栈非空 并且 遇到局部峰值
            while (!st.empty() && heights[st.top()] >= heights[i]) {
                int cur = st.top();
                st.pop();
                res = max(res, heights[cur] * (st.empty() ? i : (i - st.top() - 1)));
            }
            st.push(i); // 栈存放下标
        }
        return res;
    }
};